Russell's Paradox

A logical contradiction in {set theory}

discovered by the British mathematician {Bertrand Russell}

(1872-1970). If R is the set of all sets which don't contain

themselves, does R contain itself? If it does then it doesn't

and vice versa.

The paradox stems from the acceptance of the following

{axiom}: If P(x) is a property then

{x : P}

is a set. This is the {Axiom of Comprehension} (actually an

{axiom schema}). By applying it in the case where P is the

property "x is not an element of x", we generate the paradox,

i.e. something clearly false. Thus any theory built on this

axiom must be inconsistent.

In {lambda-calculus} Russell's Paradox can be formulated by

representing each set by its {characteristic function} - the

property which is true for members and false for non-members.

The set R becomes a function r which is the negation of its

argument applied to itself:

r ◦ \ x . not (x x)

If we now apply r to itself,

r r ◦ (\ x . not (x x)) (\ x . not (x x))

◦ not ((\ x . not (x x))(\ x . not (x x)))

◦ not (r r)

So if (r r) is true then it is false and vice versa.

An alternative formulation is: "if there is a (clean-shaven)

barber of Seville who shaves all men in Seville who don't

shave themselves, and only those men, who shaves the barber?"

This can be taken simply as a proof that no such barber can

exist whereas seemingly obvious axioms of {set theory} suggest

the existence of the paradoxical set R.

{Zermelo Fr�nkel set theory} is one "solution" to this

paradox. Another, {type theory}, restricts sets to contain

only elements of a single type, (e.g. integers or sets of

integers) and no type is allowed to refer to itself so no set

can contain itself.

A message from Russell induced {Frege} to put a note in his

life's work, just before it went to press, to the effect that

he now knew it was inconsistent but he hoped it would be

useful anyway.

(1995-03-25)